1. Field of Invention
The present invention relates generally to the field of predicate evaluation. More specifically, the present invention is related to method for evaluating a conjunction of equity and range predicates using a constant number of operations.
2. Discussion of Related Art
Conjunctive predicates (e.g., p1 AND p2 AND . . . ) are the most common kind of predicate used in querying databases. The standard way to evaluate a conjunction of predicates on a record is via a method of the form:
for each predicate do:  extract the fields that this predicate is over  if record satisfies predicate continue  else return that the record does not satisfy predicate// every predicate has been verifiedreturn that the record satisfies predicate
The performance of this predicate evaluation is a significant fraction of overall query performance in modern high-performance business intelligence (BI) engines that do large amounts of data scans. But at least three drawbacks make this standard method of predicate evaluation to be slow and have variable performance.
First, in prior art predicate evaluations, the evaluation time varies based on the number of predicates to be applied. For example, in the paper by Holloway et al. titled “How to Barter Bits for Chronons: Compression and Bandwidth Trade Offs for Database Scans”, it was found that each extra field that is touched adds about 6-8 cycles per record for a scan, which, in turn, causes variability in scan performance.
Second, in prior art predicate evaluations, each field needs to be extracted before predicates are applied. The cost associated with such an operation is expensive, especially in newer databases where fields are not aligned at machine-word (64-bit) boundaries.
Third, in prior art predicate evaluations, the loop condition and the predicate evaluation within the loop both result in conditional branch statements. Mispredicted branches cost orders of magnitude more than regular instructions on almost all modern processors (e.g., we have timed at 40 cycles on a Pentium® family processor).
Whatever the precise merits, features, and advantages of such prior art predicate evaluations, none of them achieves or fulfills the purposes of the present invention.